#include "myTree.h"
#include <set>
#include <algorithm>
using namespace std;

TreeNode::TreeNode(char a, TreeNode *left, TreeNode *right, NodeTag l, NodeTag r)
{
    data=a;
    leftChild=left;
    rightChild=right;
    lTag=l;
    rTag=r;
}

TreeNode::TreeNode()
{
    data='\0';
    leftChild=NULL;
    rightChild=NULL;
    lTag=Link;
    rTag=Link;
}

void TreeNode::printNode()
{
    cout << this->data;
}

MyTree::MyTree()
{
    root=NULL;
    isThread=false;
}

TreeNode *MyTree::maketree(const char elemList[], int &location)
{
    if(elemList[location]=='\0'||elemList[location]=='@')
    {
        location++;
        return NULL;
    }
    TreeNode *newNode = new TreeNode(elemList[location], NULL, NULL, Link, Link);
    location++;

    newNode->leftChild = maketree(elemList, location);//递归调用，用剩下的字符创建左子树
    newNode->rightChild = maketree(elemList, location);//右子树

    return newNode;
}

TreeNode *MyTree::maketree(TreeNode *tree)
{
    if(tree==NULL)
    {
        return NULL;
    }
    TreeNode *newNode = new TreeNode(tree->data, NULL, NULL, Link, Link);
    newNode->leftChild=maketree(tree->leftChild);
    newNode->rightChild=maketree(tree->rightChild);
    return newNode;
}

void MyTree::deleteTree(TreeNode *p)
{
     if (isThread = 0)//是普通二叉树
    {
        if (p == NULL)//判断是不是结点是否为空
        {
            return;
        }
        if (p->leftChild)//判断结点是不是有左子树
            deleteTree(p->leftChild);//递归调用，销毁左子树，下面同理
        if (p->rightChild)
            deleteTree(p->rightChild);
        delete p;
        p = NULL;
    }
    else
    {  
        TreeNode *q;
        q=p;
        if (q == NULL)
        {
            return;
        }
        if (q->lTag==Link)//判断方式改变了，这里不存在没有左子树的结点，需要查看ltag
            deleteTree(q->leftChild);
        if (q->rTag==Link)
            deleteTree(q->rightChild);
        delete q;
        q = NULL;
    }
}
TreeNode::~TreeNode()
{
    
}

MyTree::MyTree(const char elemList[])
{
    isThread=0;
    int i=0;
    root=maketree(elemList,i);
}

MyTree::MyTree(const MyTree &tree)
{
    root=maketree(tree.root);
    isThread=0;
}

MyTree::~MyTree()
{
    deleteTree(root);
}

void MyTree::preOrder(TreeNode *tree)
{
    if(tree==NULL)
    {
        return;
    }
    tree->printNode();
    preOrder(tree->leftChild);
    preOrder(tree->rightChild);
}

void MyTree::preOrderTraverse()
{
    TreeNode* p=root;
    if(isThread==0)
    {
        preOrder(p);
    }
}

void MyTree::inOrder(TreeNode *tree)
{
    if(tree==NULL)
    {
        return;
    }
    inOrder(tree->leftChild);
    tree->printNode();
    inOrder(tree->rightChild);
}

void MyTree::inOrderTraverse()
{
    TreeNode* p=root;
    if(isThread==0)
    {
        inOrder(p);
    }
    else
    {
       TreeNode *p = root->leftChild;//这里的root是头节点，其左孩子为根节点
        while (p != root)
        {
            while (p->lTag == Link)//从根节点沿着左支走到头
            {
                p = p->leftChild;
            }
            cout << p->data;//访问
            while (p->rTag == Thread && p->rightChild != root)//这里是最后一个结点
            //如果有rtag为线索，直接访问后继，否则跳出循环，进入右孩子节点，并从右孩子节点进行右子树中序遍历
            {
                p = p->rightChild;
                cout << p->data;
            }
            p = p->rightChild;
        }
        p->printNode();
    }
}

void MyTree::postOrder(TreeNode *tree)
{
    if(tree==NULL)
    {
        return;
    }
    postOrder(tree->leftChild);
    postOrder(tree->rightChild);
    tree->printNode();
}

void MyTree::postOrderTraverse()
{
    TreeNode* p=root;
    if(isThread==0)
    {
        postOrder(p);
    }
}

int MyTree::leaf(TreeNode *tree)
{
    if(tree==NULL)
    {
        return 0;
    }
    if(tree->leftChild==NULL&&tree->rightChild==NULL)
    {
        return 1;
    }
    return leaf(tree->leftChild)+leaf(tree->rightChild);
}

int MyTree::countLeaf()
{
    if(isThread==0)
    {
        return leaf(root);
    }
    return 0;
}

void MyTree::height(TreeNode *tree, const int &count,int &maxcount)
{
    if(tree==NULL)
    {
        if(count>maxcount)
        {
            maxcount=count;
        }
        return;
    }
    height(tree->leftChild,count+1,maxcount);
    height(tree->rightChild,count+1,maxcount);
}

int MyTree::countHeight()
{
    int maxcount=0;
    height(root,0,maxcount);
    return maxcount;
}

bool MyTree::isThreadedTree()
{
    if(isThread==0)
    {
        return false;
    }
    return true;
}

void MyTree::inOrder(TreeNode *tree, TreeNode *nodelist[], int &location)
{
    if(tree==NULL)
    {
        return;
    }
    inOrder(tree->leftChild,nodelist,location);
    nodelist[location]=tree;
    location++;
    inOrder(tree->rightChild,nodelist,location);
}

void MyTree::inOrder(TreeNode *tree, int &count)
{
    if(tree==NULL)
    {
        return;
    }
    inOrder(tree->leftChild,count);
    count++;
    inOrder(tree->rightChild,count);
}

bool MyTree::inOrderThreading()
{
    int count=0;
    int location=0;
    inOrder(root,count);
    TreeNode **pointer=new TreeNode *[count];
    inOrder(root,pointer,location);
    for(int i=0;i<count;i++)
    {
        if(pointer[i]->leftChild==NULL)
        {
            if(i!=0)
            {
                 pointer[i]->leftChild=pointer[i-1];
            }
            pointer[i]->lTag=Thread;
        }
        if(pointer[i]->rightChild==NULL)
        {
            if(i!=count-1)
            {
                pointer[i]->rightChild=pointer[i+1];
            }
            pointer[i]->rTag=Thread;
        }
    }
    isThread=1;
    return true;
}

TreeNode &MyTree::locateNode(const char &d)
{
    TreeNode *tmp = root;
    if (locate(d, tmp))
    {
        return *locate(d, tmp);
    }
    else
    {
        TreeNode *p = new TreeNode();
        return *p;//没找着就返回空结点
    }
}
TreeNode *MyTree::locate(const char &c, TreeNode *node)
{
    if (node->data == c)//等于，直接返回
    {
        return node;
    }

    if (node->leftChild && node->lTag != Thread)//有左节点
    {
        TreeNode *p = locate(c, node->leftChild);//递归调用，在左子树里找
        if (p)
        {
            return p;
        }
    }

    if (node->rightChild && node->rTag != Thread)//有右节点
    {
        TreeNode *p = locate(c, node->rightChild);//右子树里找
        if (p)
        {
            return p;
        }
    }
    return NULL;//没找着
}

TreeNode &MyTree::preNode(const TreeNode &node)
{
    TreeNode *p = node.leftChild;
    if (node.lTag == Link)//有左子树
    {
        TreeNode *tmp = p;
        while (tmp->rTag == Link)//在左子树里往右子树找到头，就是前驱
        {
            tmp = tmp->rightChild;
        }

        return *tmp;
    }
    else//左孩子就是前驱
        return *(node.leftChild);
}
TreeNode &MyTree::nextNode(const TreeNode &node)
{
    TreeNode *p = node.rightChild;
    if (node.rTag == Link)//有右子树
    {
        TreeNode *tmp = p;
        while (tmp->lTag == Link)//在右子树里往左子树找到头
        {
            tmp = tmp->leftChild;
        }

        return *tmp;
    }
    else//右孩子就是后继
        return *(node.rightChild);
}
HuffmanTree::HuffmanTree(const int &n, const int a[])
{
    num = n;
    int *p = new int[n];//没法对const数组排序
    for (int i = 0; i < n; i++)
    {
        p[i] = a[i];
    }
    sort(p, p + n, greater<int>());//从大到小，weight递减
    HFT = new HFNode[n * 2];
    initleaves(n, p);
    generateCodes(n*2 - 1, "");//这里从最大的结点，也就是最后一个结点生成霍夫曼编码，这个结点的code是""
    delete[] p;
}
HuffmanTree::~HuffmanTree()
{
    delete[] HFT;
}
void HuffmanTree::initleaves(int n, const int *data)//初始化每个叶子节点，也就是数据节点
{
    if (n <= 1)
        return;
    int m = 2 * n - 1; // 数组共2n - 1个元素，n个元素，每两个加起来，再加n-1个
    for (int i = 1; i <= m; i++)
    {
        HFT[i].parent = 0;
        HFT[i].left = 0;
        HFT[i].right = 0;
    }
    for (int i = 1; i <= n; i++)
        HFT[i].weight = data[i - 1];//从1到n记录叶子节点
    for (int i = n + 1; i <= m; i++) // 产生的新结点要放在从n+1开始，一直到2n-1的位置
    {
        int s1, s2;
        selectMin(HFT, i, s1, s2);//挑选权值最小的结点在的位置
        HFT[s1].parent = i;
        HFT[s2].parent = i; // 现在的i号结点变为这两个节点的双亲
        HFT[i].left = s1;//左孩子s1
        HFT[i].right = s2;//右孩子s2
        HFT[i].weight = HFT[s1].weight + HFT[s2].weight;//权重为两者之和
    }
}
void HuffmanTree::selectMin(HFNode *hft, int n, int &s1, int &s2)
{
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0)//没有双亲，说明这个结点还没用过
        {
            s1 = i;
            break;
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0 && HFT[i].weight < HFT[s1].weight)//找权值最小的
        {
            s1 = i;
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0 && i!= s1 )
        {
            s2 = i;
            break;
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (HFT[i].parent == 0 && HFT[i].weight < HFT[s2].weight&&i!=s1)//找第二小的
        {
            s2 = i;
        }
    }
}

void HuffmanTree::generateCodes(int idx, string code)
{
    HFT[idx].code = code;//传入现在结点的code
    if (HFT[idx].left)
    {
        generateCodes(HFT[idx].left, code + "0");//给左子树生成霍夫曼编码，每往左子树走一次，编码加一个0
    }
    if (HFT[idx].right)
    {
        generateCodes(HFT[idx].right, code + "1");//给右子树生成霍夫曼编码，每往右子树走一次，编码加一个1
    }
}
void HuffmanTree::printHuffmanCodes()
{
    for (int i = 1; i <= num; i++)
    {
        cout << HFT[i].weight << ":" << HFT[i].code << endl;
    }
}
